package m202405.d16;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/16 18:16
 */
public class Q152 {

    /**
     * maxDp[i]表示包含nums[i]进行乘法运算的最大积
     * minDp[i]表示包含nums[i]进行乘法运算的最小积
     * [2,3,-2,4]
     * --
     * maxDp[0] = 2 minDp[0] = 2
     * --
     * maxDp[1] = max(maxDp[0]*3,minDp[0]*3,3) = max(6,6,3) = 6
     * minDp[1] = min(minDp[0]*3,maxDp[0]*3,3) = min(6,6,3) = 3
     * --
     * maxDp[2] = max(maxDp[1]*-2,minDP[1]*-2,-2) = max(-12,-6,-2) = -2
     * minDp[2] = min(minDp[1]*-2,maxDP[1]*-2,-2) = min(-6,-12,-2) = -12
     * --
     * maxDp[3] = max(maxDp[2]*4,minDp[2]*4,4) = max(-8,-48,4) = 4
     * minDp[3] = min(minDp[2]*4,maxDp[2]*4,4) = min(-48,-8,4) = -48
     */
    public int maxProduct(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] maxDp = new int[nums.length];
        int[] minDp = new int[nums.length];
        maxDp[0] = nums[0];
        minDp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxDp[i] = Math.max(maxDp[i - 1] * nums[i], Math.max(minDp[i - 1] * nums[i], nums[i]));
            minDp[i] = Math.min(minDp[i - 1] * nums[i], Math.min(maxDp[i - 1] * nums[i], nums[i]));
            max = Math.max(max, maxDp[i]);
        }
        return max;
    }
}
